第9章虚拟内存

为了更有效地管理内存并且少出错，现代系统提供了一种对主存的抽象概念，叫做虚拟内存(VM)。虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的俺没交互，它为每个进程提供了一个大的、一致的和私有的地址空间。通过一个很清晰的机制，虚拟地址内存提供了三个重要的能力:

它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
它为每个进程提供了一致的地址空间，从而简化了内存管理。
它保护了每个进程的地址空间不被其他进程破坏。

1、物理和虚拟地址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每字节都有一个唯一地物理地址(Physical Address, PA)。第一个字节的地址为0，接下来的字节地址为1，再下一个为2，以此类推。给这种简单的结构，CPU访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址。

早期的PC使用物理地址，而且诸如数字信号处理器、嵌入式微控制器以及Cray超级计算机这样的系统仍然继续使用这种寻址方式。然而现代处理器使用的是一种称为虚拟寻址的寻址形式。如下图：

使用虚拟寻址，CPU通过生成一个虚拟地址(Virtual Address, VA)来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。CPU芯片上叫做内存管理单元(Memory Management Unit， MMU)的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

2、地址空间

在一个带虚拟内存的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址，这个地址空间被称为虚拟地址空间。一个地址空间的大小由表示表示最大地址所需要的位数来描述，可以把前面这个由N个虚拟地址组成的虚拟空间叫做一个n位地址空间。现代系统通常支持32位或者64位虚拟地址空间。

一个系统还有一个物理地址空间，内存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

3、虚拟内存作为缓存的工具

概念上而言，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每字节都有一个唯一地虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。和存储器层次结构中其它缓存一样，磁盘(较低层)上的数据被分割成块，这些块作为磁盘和主存(较高层)之间的传输单元。

VM系统通过将虚拟内存分割为称为虚拟页(Virtual Page， VP)的大小固定的块来处理这个问题。每个虚拟页的大小为P=2^p字节。类似地，物理内存被分割为物理页(Physical Page，PP)，大小也为P字节(物理页也被称为页帧)。

在任意时刻，虚拟页面的集合都分为三个不想交的子集:

未分配的：VM系统还未分配(或者创建)的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
缓存的：当前已缓存在物理内存中的已分配页。
未缓存的：未缓存在物理内存中的已分配页。

3.1 DRAM缓存的组织结构

术语SRAM缓存用来表示位于CPU和主存之间的的L1、L2和L3高速缓存，DRAM用来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

在存储层次结构中，DRAM缓存的位置对它的组织结构有很大的影响。回想一下，DRAM比SRAM要慢大约10倍，而磁盘要比DRAM慢大约100 000多倍。一次DRAM缓存中的不命中比起SRAM缓存中的不命中要昂贵的多，这是因为DRAM缓存不命中要由磁盘来服务，而SRAM缓存不命中通常是由基于DRAM的主存来服务的。而且，从磁盘的第一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节慢大约100 000倍。（后续字节被缓存在主存中）

因为大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通常是4KB~2MB。因为大的不命中处罚，DRAM缓存是全相联的，即任何虚拟页都可以放置在任何的物理页中。同时不命中时的替换策略也很重要，故与硬件对SRAM缓存相比，操作系统对DRAM缓存使用了更加精密的替换算法。最后，因为对磁盘的访问时间很长，DRAM缓存总是使用写回，而不是写直达。

3.2 页表

同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在DRAM中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换这个牺牲页。

这些功能是由软硬件联合提供的，包括操作系统软件、MMU(内存管理单元)中的地址翻译硬件和一个存放在物理内存中叫做页表的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表内容，以及在磁盘与DRAM之间来回传送页。

下图展示了一个页表的基本组织结构。页表就是一个页表条目(Page Table Entry， PTE)的数组。虚拟地址空间中的每个页中一个固定偏移量处都有一个PTE。假设每个PTE都由一个有效位和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始地址。如果没有设置有效位，那么一个空地址表示这个虚拟页还未分配。否则，这个地址就指向该虚拟页在磁盘上的起始位置。

上图展示了一个有8个虚拟页和4个物理页的系统的页表。四个虚拟页(VP1、VP2、VP4和VP7)当前被缓存在DRAM中。两个页(VP0和VP5)还未被分配，而剩下的页(VP3和VP6)已经被分配了，但是当前还未被缓存。

3.3 页命中

考虑一下当CPU想要读包含在VP2中的虚拟内存的一个字时会发生什么，VP2被缓存在DRAM中。使用地址翻译技术，地址翻译硬件将虚拟地址作为一个索引来定位PTE2，并从内存中读取它。因为设置了有效位，那么地址翻译硬件就知道VP2是缓存在内存中的了。所以它使用PTE中的物理内存地址(该地址指向PP1中缓存页的起始位置)，构造出这个字的物理地址。

3.4 缺页

在虚拟内存的习惯说法中，缓存不命中称为缺页。下图展示了在缺页之前我们的示例页表的状态。CPU引用了VP3中的一个字，VP3并未缓存在DRAM中。地址翻译硬件从内存中读取PTE3，从有效位推断出VP3未被缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4。如果VP4已经被修改了，那么内核就会将它复制回磁盘。无论哪种情况，内核都会修改VP4的页表条目。

接下来，内核从磁盘复制VP3到内存中的PP3，更新PTE3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP3已经缓存在主存中了，那么页命中也能由地址翻译硬件正常处理了。下图展示了在缺页之后我们的示例页表的状态。

3.5 分配页面

当我们调用malloc等分配一个新的虚拟页VP5时，主要是在磁盘上创建空间并更新PTE5，使它指向这个新创建的页面。

3.6 又是局部性救了我们

虚拟内存能工作好，主要归功于局部性。尽管在整个运行过程中程序引用的不同的页面的总数可能会超过物理内存总的大小，但是局部性原则保证了在任意时刻，程序趋向于在一个较小的活动页面集合上工作。这个集合叫做工作集合或者常驻集合。

有时程序可能不会表现出良好的时间局部性。如果工作集的大小超过了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动，这时页面将会不断换入换出，程序就会很慢，我们也该想想是不时设计出了问题，并尝试解决抖动。

内存抖动最常见的例子应该就是数组的按行访问和按列访问了，按行访问明显会好一点。

4、虚拟内存作为内存管理的工具

实际上，操作系统为每一个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间，而且多个虚拟页面也可以映射到同一个物理页面上。

按需页面调度和独立的虚拟地址空间的结合，对系统内存的使用和管理造成了深远的影响。VM简化了加载和链接、代码和数据的共享，以及应用程序的内存分配：

简化链接
独立地址空间允许每个进程的内存映像使用相同的基本格式。例如在64位x86-64平台上，代码段总是从虚拟地址0x400000开始。数据段跟在代码段后，中间夹杂着对齐空白。栈占据用户进程地址空间的最高部分0x7fffffff，并向下增长。这样的一致性极大地简化了链接器的设计和实现，运行链接器生成完全连接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
简化加载
把目标文件（可执行文件和共享对象文件）中的.text和.data加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把他们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。然而，加载器从不从磁盘复制任何数据到内存中，而在每个页被初次引用时，或CPU取指令时，或一条正在执行的指令引用一个内存位置时，虚拟内存系统会按需自动调入数据页。
简化共享
一般情况下，每个进程都有自己私有的代码、数据、堆、以及栈区域，是不和其他进程共享的。在这种情况下，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。在部分情况下，进程间还是需要共享代码和数据的，例如每个C程序都会调用C标准库中的程序（printf）、都需要调用相同的内核代码。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本。
简化内存分配
当运行在用户进程的程序要求额外的堆空间时（如调用malloc），操作系统分配k个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的k个任意的物理页面。由于页表的存在，操作系统没必要分配k个连续的物理页面，页面可随机地分散在物理内存中。

5、虚拟内存作为内存保护的工具

可以通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。比如每个PTE中已经添加了三个许可位，SUP位表示进程能否必须运行在内核模式才能访问该页，READ位和WRITE位控制对页面的读和写访问。

如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核的异常处理程序。Linux shell一般将这种异常报告为“段错误segmentation fault”。

6 地址翻译

形式上来说，地址翻译是一个N元素的虚拟地址空间(VAS)的元素和一个M元素的物理地址空间(PAS)中元素之间的映射，

这里

下图展示了MMU如何利用页表来实现这种映射。CPU中的一个控制寄存器，页表基址寄存器(Page Table Base Register, PTRB)指向当前页表。n位的虚拟地址包含两个部分:一个p位的虚拟页面偏移(Virtual Page Offset, VPO)和一个(n-p)位的虚拟页号(Virtual Page Number， VPN)。MMU利用VPN来选择适当的PTE。例如，VPN0选择PTE 0，VPN1选择PTE 1，以此类推。将页表条目中物理页号(Physical Page Number，PPN)和虚拟地址中的VPO串联起来，就得到相应的物理地址。

下面来讨论一下页面命中和不命中的处理过程。页面命中完全由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成。
当页面命中时，CPU硬件执行步骤如下：

(1)、处理器生成一个虚拟地址，并把它传给MMU
(2)、MMU生成PTE地址，并从高速缓存/主存请求得到它（这一步是因为页表是在内存中）
(3)、高速缓存/主存向MMU返回PTE
(4)、MMU构造物理地址，并把它传送给高速缓存/主存
(5)、高速缓存/主存返回所请求的数据给处理器

缺页时，硬盘和操作系统内核协作完成如下：

(1)、处理器生成一个虚拟地址，并把它传给MMU
(2)、MMU生成PTE地址，并从高速缓存/主存请求得到它（这一步是因为页表是在内存中）
(3)、高速缓存/主存向MMU返回PTE
(4)、PTE有效位是0，MMU出发一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
(5)、缺页异常处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到硬盘。
(6)、缺页异常处理程序页面调入新的页面，并更新内存中的PTE。
(7)、缺页异常处理程序返回到原来的进程中，再次执行指令，这次就会命中。

6.1 结合高速缓存和虚拟内存

在任何既使用虚拟内存又使用SRAM高速缓存的系统中，都有因该使用虚拟地址还是物理地址来访问SRAM高速缓存的问题。大多数的系统都选择物理寻址，使用物理寻址，就可以将页表（条目）也加载到高速缓存并能像访问其他存储块一样访问。而且高速缓存也无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

处理器（虚拟内存地址）——————>MMU——————>高速缓存——————>内存。

6.2 利用TLB加速地址翻译

为了降低从内存取PTE的开销，许多系统在MMU中引入了一个关于PTE的小的缓存，称为翻译后备缓冲器（TLB，快表）。

TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由PTE组成的块。如果TLB有T=2^t个组，那么TLB索引（TLBI）是由VPN的t个最低位组成的，而TLB标记（TLBT）是由VPN中剩余的位组成的。

如果TLB命中，则取出对应的PTE并生成物理地址并访问高速缓存/主存获取请求的数据，如果不命中，则到高速缓存/内存中去取PTE，并放到TLB中，可能会覆盖。

6.3 多级页表

为什么要使用多级页表？假设有一个32位的地址空间，每个页4KB，那么需要2^20个PTE来进行表示，又如果每条PTE占4Byte，那么总的需要4M的内存空间来存储页表。而这只是32位地址情况，如果是64位就又会复杂很多。

假设一个上述32位虚拟地址空间有如下形式：内存的前2K个页面分配给了代码和数据，接下来6K个页面未分配，再接下来的1023个也未分配，接下来的1个页面分配给了用户栈。下图展示了如何为虚拟空间构造一个两级也表层次结构:

多级页表从两个方面减少了内存要求：

如果一级页表中的一个PTE为空，那么对应的二级页表就不存在。这能带来很大的结局，通常一个4GB的虚拟进程空间的大部分都是未分配的。
只有一级页表才需要总是存在主存中。而二级页表只有在需要时才进行创建、页面调入和调出，能极大地减少主存的压力，只有常用的二级页表才需要缓存在主存中。

7 参考

参考书籍：《深入理解计算机系统》
参考链接：https://blog.csdn.net/longbei9029/article/details/79281273

第9章 虚拟内存